6章 パーティショニング
どういった時にパーティショニングが必要になるか
単一のマシンで保存や処理をするのが現実的ではないほどのデータがある場合
それぞれのパーティションはシェアードナッシング（水平スケーリング）クラスタの別々のノードに配置できる
パーティショニングの目標
データやクエリの負荷を複数のマシン間で均等に分配してホットスポット（不均衡に高い負荷がかかるノード）が生じないようにする
パーティショニングのアプローチ
キーの範囲によるパーティショニング
skewがあるとパーティションの効果が大きく損なわれる。 最もシンプルな方法はレコードをランダムに割り当てること
あるアイテムがあるノードがどのパーティションにあるかわからないので、全てのノードに対して並列でクエリを実行する必要がある
アクセスパターンによってはホットスポットが生じうる。
キーの先頭の要素に元々のキーの要素とは別の要素を使う（例えばセンサーの計測のタイムスタンプとセンサー名）
HBase、RethinkDB、MongoDBなど
ハッシュパーティショニング
キーに対するパーティション設定の決定にハッシュ関数を使用
ハッシュ関数は暗号としての強度は必要ない（JavaのObject.hashCode()やRubyのObject#hashはプロセッサが異なると同じキーに対して異なるハッシュ値が返される）
キーの範囲によるパーティションの範囲に対するクエリの実効性は失われる
MongoDBはハッシュベースのシャーディングモードを有効にすると範囲に対するクエリは必ず全てのパーティションに送られる
Cassandraは複数の列から構成される複合プライマリキーの先頭部分の先頭部分のハッシュをパーティションの決定に使用する
パーティショニングとセカンダリインデックスとの関係
セカンダリインデックスの問題点である、パーティションに対応づけられないことでそのためのアプローチは2つ
ドキュメントによってパーティショニングされたインデックス
主キーのインデックスとは別で（例えばドキュメントで）パーティショニングされたセカンダリインデックスを持つ
table:partition0-primary-key-index
primary key color make location
191 red Honda Palo Alto
214 black Dodge San Jose
306 red Ford Sunnyvale
table:partition0-secondary-index
color:black 214
color:red 191, 306
color:yellow
make:Dodge 214
make:Ford 306
make:Honda 191
table:partition1-primary-key-index
primary key color make location
515 silver Ford Milpitas
768 red Volvo Cupertino
893 silver Audi Santa Clara
table:partision1-secondary-index
color:black
color:red 768
color:silver 515, 893
make:Audi 893
make:Ford 515
make:Volvo 768
赤い車の検索は全てのパーティションに送信して得られた情報を結合する必要がある（スキャッタ/ギャザー）
語によってパーティショニングされたインデックス
全てのパーティションのデータをカバーするグローバルインデックスを語（ドキュメントに現れる全ての単語）構築し、グローバルインデックスをパーティショニングする
読み取りを効率的にできる（調べたい語を含むパーティションにリクエストを送信すれば良いので）
書き込みが低速で複雑になる
グローバルなセカンダリインデックスの更新は非同期なので直前の変更がインデックスに反映されていないかもしれない
語でパーティショニングすれば範囲に対するスキャンが有効になり、語のハッシュであれば負荷の分散が均等になる
DynamoDB、Riakの検索機能、Oracle
クエリを適切なパーティションにルーティングする手法
リクエストのルーティング
サービスディスカバリ問題へのアプローチ
任意のノードに接続して、そのノードがたまたま対象のノードならリクエストを処理、そうでなければそのノードは適切なノードに転送して結果を受信して結果をクライアントに返す。
クライアントからの全てのリクエストをルーティング層に送信し、ルーティング層が各リクエストを処理するノードを判断して転送する。
クライアントにパーティショニングとノードへのパーティションの割り当てを認識させる。（クライアントに直接適切なノードに接続させる）
ロードバランシング
取るべきではない方法：ハッシュの剰余
$ hash(key) mod Nで割り当てる場合、ノード数$ Nが変化すると、ほとんどのキーはノード間で移動しなければならないのでリバランシングの負担が大きい
パーティション数の固定
Riak、Elasticsearch、Couchbase、Voldmortなど
データセットの合計数が大きく変動する場合は適切なパーティション数を設定するのが難しく、パーティションが小さすぎればオーバーヘッドが大きくなり、大きすぎるとリバランシングやノード障害からのリカバリの負担が大きくなる。
動的なパーティション数
パーティション数をデータの送料に適合させられる。
空のデータベースが単一のパーティションからスタートしてしまう可能性がある
HBaseやMongoDBは空のデータベースに対して初期のパーティション群を設定できる。（事前分割）
事前分割するにはユーザーがキーの分布を把握している必要がある
ノード数に比例するパーティション数
多数のパーティションに対して平均すれば、新しいノードと既存のノードと均等に負荷を受け持つようになる。
Cassandraなは不均等な分割を回避するリバランシングの独自アルゴリズムを持つ。
並列クエリ実行エンジン
大規模並列処理(MPP:massively parallel processing)のクエリオプティマイザは複雑なクエリをいくつもの実行ステージとパーティションに分割し、その多くはデータベースクラスタ内の複数のノード上で並列に処理される。
あるパーティションへの書き込みには成功したが、他のパーティションへの書き込みに失敗したら？